package linkedlist;

/**
 * 两两交换链表
 */
public class SwapNodesInPairs {
  /**
   * 使用递归，从右到左进行交换
   *
   * @param head
   * @return
   */
  public ListNode swapPairs1(ListNode head) {
    if (head.next == null || head == null) {
      return head;
    }
    ListNode next = swapPairs1(head.next.next);
    ListNode pre = head.next;
    head.next = next;
    pre.next = head;
    return pre;
  }

  /**
   *使用迭代，从左到右进行遍历
   * @param head
   * @return
   */
  public ListNode swapPairs2(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode cur = head;
    head = head.next;
    //这是一个工具节点，用来指示当前节点的上一个节点
    ListNode last = new ListNode(-1);
    while (cur != null && cur.next != null) {
      ListNode next = cur.next.next;
      ListNode prev = cur.next;

      prev.next = cur;
      cur.next = next;
      last.next = prev;

      last = cur;
      cur = next;
    }
    return head;
  }
}
